package algo.utilitaire;

import algo.graphe.Graphe;
import algo.graphe.Noeud;
import java.util.LinkedList;
import java.util.NoSuchElementException;

/**
 * Outils qui fait tout les calculs de Dijkstra
 * @author <a href="mailto:christian.dramsy@gmail.com">DRAMSY Christain</a>
 */
public class UtilitaireDijkstra {

    /**
     * Effectue l'algorithme de moore dijkstra V1 c'est à dire avec les tableau
     * @param start
     * @param graphe 
     * @param displayResult Booleen qui permet de determiner si on affiche le resultat ou pas.
     */
    public static void DijkstraTableau(int start, Graphe graphe, boolean displayResult) {
        try {
            if (!graphe.isConnexe()) {
                System.out.println("Le graphe doit être connexe");
                return;
            }
        } catch (NullPointerException e) {
            return;
        }
        //  C l'ensemble des noeud déjà visité
        boolean[] visited = new boolean[graphe.getOrdre()];
        for (int i = 0; i < graphe.getOrdre(); i++) {
            visited[i] = false;
        }
        int ordre = graphe.getOrdre();
        //  Le cout du chemin de beginNode au node autres sommet(indice du tableau)->correcpond au d(i) dans le sujet
        int[] distance = new int[ordre];
        //  Tableau contenant l'antecedant d'un sommet
        int[] antecedant = new int[ordre];
        //  On initialise toute les distances à INFINI et ls antecedant à -1
        for (int i = 0; i < ordre; i++) {
            antecedant[i] = -1;
            distance[i] = Integer.MAX_VALUE;
        }
        int pivot = start;
        // C = 1
        visited[pivot] = true;

        //  d(1) = 0 , d(i) = infini pour tout i != 1
        distance[pivot] = 0;

        boolean allNodeVisited = false;

        while (!allNodeVisited) {
            allNodeVisited = true;
            int nbNonVisite = 0;
            //  verification si tout les noeurs ont été visité
            for (int i = 0; i < ordre; i++) {
                if (visited[i] == false) {
                    nbNonVisite++;
                    if (nbNonVisite > 1) {
                        allNodeVisited = false;
                        break;
                    }
                }
            }

            if (allNodeVisited) {
                break;
            }
            //  recuperation des successeurs
            boolean[] successeurs = graphe.successeurs(pivot);
            //  Pout tou x pas encore visité et successeur de pivot
            for (int x = 0; x < ordre; x++) {
                //  pas encore visité et successeur de pivot
                if (!visited[x] && successeurs[x] == true) {
                    if (distance[pivot] + graphe.getMatriceAdjValue(pivot, x) < distance[x]) {
                        distance[x] = distance[pivot] + graphe.getMatriceAdjValue(pivot, x);
                        antecedant[x] = pivot;
                    }
                }
            }

            //  Trouver dans les sommets pas encore visité y de plus petite distance
            int min = Integer.MAX_VALUE;
            int y = -1;

            for (int i = 0; i < ordre; i++) {
                if (!visited[i] && min > distance[i]) {
                    min = distance[i];
                    y = i;
                }
            }
            //  Si y == -1 on revient au debut
            pivot = y;
            if (pivot == -1) {
                break;
            }
            visited[pivot] = true;
        }
        if (displayResult) {
            UtilitaireAffichage.afficherResultatDijkstra(distance, antecedant, start);
        }
    }

    /**
     * Effectue l'algorithme de moore dijkstra V3 c'est à dire avec les listes chainées
     * @param start
     * @param graphe 
     * @param displayResult Booleen qui determine si on affiche un resultat ou pas
     */
    public static void DijkstraListe(int start, Graphe graphe, boolean displayResult) {
        try {
            if (!graphe.isConnexe()) {
                System.out.println("Le graphe doit être connexe");
                return;
            }
        } catch (NullPointerException e) {
            return;
        }

        //  C l'ensemble des noeud déjà visité
        boolean[] visited = new boolean[graphe.getOrdre()];
        for (int i = 0; i < graphe.getOrdre(); i++) {
            visited[i] = false;
        }
        int ordre = graphe.getOrdre();
        //  Le cout du chemin de beginNode au node autres sommet(indice du tableau)->correcpond au d(i) dans le sujet
        int[] distance = new int[ordre];
        //  Tableau contenant l'antecedant d'un sommet
        int[] antecedant = new int[ordre];
        //  On initialise toute les distances à INFINI et ls antecedant à -1
        for (int i = 0; i < ordre; i++) {
            antecedant[i] = -1;
            distance[i] = Integer.MAX_VALUE;
        }
        int pivot = start;
        // C = 1
        visited[pivot] = true;

        //  d(1) = 0 , d(i) = infini pour tout i != 1
        distance[pivot] = 0;

        boolean allNodeVisited = false;

        while (!allNodeVisited) {
            allNodeVisited = true;
            int nbNonVisite = 0;
            //  verification si tout les noeuds ont été visité
            for (int i = 0; i < ordre; i++) {
                if (visited[i] == false) {
                    nbNonVisite++;
                    if (nbNonVisite > 1) {
                        allNodeVisited = false;
                        break;
                    }
                }
            }

            if (allNodeVisited) {
                break;
            }
            //  recuperation des successeurs
            boolean[] successeurs = graphe.successeurs(pivot);
            //  Pout tou x pas encore visité et successeur de pivot
            for (int x = 0; x < ordre; x++) {
                //  pas encore visité et successeur de pivot
                if (!visited[x] && successeurs[x] == true) {
                    if (distance[pivot] + graphe.getMatriceAdjValue(pivot, x) < distance[x]) {
                        distance[x] = distance[pivot] + graphe.getMatriceAdjValue(pivot, x);
                        antecedant[x] = pivot;
                    }
                }
            }

            //  Trouver dans les sommets pas encore visité y de plus petite distance
            int min = Integer.MAX_VALUE;
            int y = -1;
            LinkedList<Noeud> list = graphe.creerStructureListeChainee().get(pivot);
            Noeud tmp;
            while (true) {
                try {
                    tmp = list.removeFirst();
                    if (!visited[tmp.getNum()] && min > distance[tmp.getNum()]) {
                        min = distance[tmp.getNum()];
                        y = tmp.getNum();
                    }
                } catch (NoSuchElementException e) {
                    break;
                }
            }
            //  Si y == -1 on revient au debut
            pivot = y;
            if (pivot == -1) {
                break;
            }
            visited[pivot] = true;
        }

        if (displayResult) {
            UtilitaireAffichage.afficherResultatDijkstra(distance, antecedant, start);
        }
    }

    /**
     * Execute l'algorithme de Moore Dijkstra sur un graphe
     * @param graphe 
     * @param displayResult Booleen permet de determiner si on affiche le resultat ou pas
     */
    public static void executeDijkstraTableau(Graphe graphe, boolean displayResult) {
        try {
            if (!graphe.isConnexe()) {
                System.out.println("Le graphe doit être connexe");
                return;
            }
            for (int i = 0; i < graphe.getOrdre(); i++) {
                UtilitaireDijkstra.DijkstraTableau(i, graphe, displayResult);
            }
        } catch (NullPointerException e) {
        }
    }

    /**
     * Execute l'algorithme de Moore Dijkstra sur un graphe
     * @param graphe 
     * @param displayResult Booleen permet de determiner si on affiche le resultat ou pas
     */
    public static void executeDijkstraListe(Graphe graphe, boolean displayResult) {
        try {
            if (!graphe.isConnexe()) {
                System.out.println("Le graphe doit être connexe");
                return;
            }
            for (int i = 0; i < graphe.getOrdre(); i++) {
                UtilitaireDijkstra.DijkstraListe(i, graphe, displayResult);
            }
        } catch (NullPointerException e) {
        }
    }

    /**
     * Effectue l'algorithme de moore dijkstra V2 c'est à dire avec les Tas
     * @param start
     * @param le graphe 
     * @param displayResult Booleen permet de determiner si on affiche le resultat ou pas
     */
    public static void DijkstraTas(int start, Graphe graphe, boolean displayResult) {
        try {
            if (!graphe.isConnexe()) {
                System.out.println("Le graphe doit être connexe");
                return;
            }
        } catch (NullPointerException e) {
            return;
        }
        //  C l'ensemble des noeud déjà visité
        boolean[] visited = new boolean[graphe.getOrdre()];
        for (int i = 0; i < graphe.getOrdre(); i++) {
            visited[i] = false;
        }
        int ordre = graphe.getOrdre();
        //  Le cout du chemin de beginNode au node autres sommet(indice du Tas)->correcpond au d(i) dans le sujet
        int[] distance = new int[ordre];
        //  Tas contenant l'antecedant d'un sommet
        int[] antecedant = new int[ordre];
        //  On initialise toute les distances à INFINI et ls antecedant à -1
        for (int i = 0; i < ordre; i++) {
            antecedant[i] = -1;
            distance[i] = Integer.MAX_VALUE;
        }
        // C = 1
        visited[start] = true;
        Noeud[] tas = new Noeud[0];
        Noeud pivot = new Noeud(start, 0);


        //  d(1) = 0 , d(i) = infini pour tout i != 1
        distance[start] = 0;

        /**
         * Boucle principale 
         */
        while (true) {
            if (tas == null) {
                break;
            }
            //  recuperation des successeurs
            boolean[] successeurs = graphe.successeurs(pivot.getNum());
            //  Pout tou x pas encore visité et successeur de pivot
            for (int x = 0; x < ordre; x++) {
                //  pas encore visité et successeur de pivot
                if (successeurs[x] == true) {
                    if (distance[pivot.getNum()] + graphe.getMatriceAdjValue(pivot.getNum(), x) < distance[x]) {
                        distance[x] = distance[pivot.getNum()] + graphe.getMatriceAdjValue(pivot.getNum(), x);
                        antecedant[x] = pivot.getNum();
                        if (!visited[x]) {
                            tas = UtilitaireTas.ajouter(tas, new Noeud(x, distance[x]));
                        }
                    }
                }
            }
            try {
                pivot = tas[0];
            } catch (ArrayIndexOutOfBoundsException ex) {
                break;
            }
            tas = UtilitaireTas.suppressionRacine(tas);
        }

        if (displayResult) {
            UtilitaireAffichage.afficherResultatDijkstra(distance, antecedant, start);
        }
    }

    /**
     * Execute l'algorithme de Moore Dijkstra sur un graphe
     * @param graphe 
     * @param displayResult Booleen permet de determiner si on affiche le resultat ou pas
     */
    public static void executeDijkstraTas(Graphe graphe, boolean displayResult) {
        try {
            if (!graphe.isConnexe()) {
                System.out.println("Le graphe doit être connexe");
                return;
            }
            for (int i = 0; i < graphe.getOrdre(); i++) {
                UtilitaireDijkstra.DijkstraTas(i, graphe, displayResult);
            }
        } catch (NullPointerException e) {
        }
    }
}
